/*
 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under both the BSD-style license (found in the
 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
 * in the COPYING file in the root directory of this source tree).
 * You may select, at your option, one of the above-listed licenses.
 */

/*-**************************************
 *  Tuning parameters
 ****************************************/
#define MINRATIO 4 /* minimum nb of apparition to be selected in dictionary */
#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO)

/*-**************************************
 *  Compiler Options
 ****************************************/
/* Unix Large Files support (>4GB) */
#define _FILE_OFFSET_BITS 64
#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */
#define _LARGEFILE_SOURCE
#elif !defined(__LP64__) /* No point defining Large file for 64 bit */
#define _LARGEFILE64_SOURCE
#endif

/*-*************************************
 *  Dependencies
 ***************************************/
#include <stdio.h>  /* fprintf, fopen, ftello64 */
#include <stdlib.h> /* malloc, free */
#include <string.h> /* memset */
#include <time.h>   /* clock */

#include "fse.h" /* FSE_normalizeCount, FSE_writeNCount */
#include "mem.h" /* read */
#define HUF_STATIC_LINKING_ONLY
#include "divsufsort.h"
#include "huf.h"           /* HUF_buildCTable, HUF_writeCTable */
#include "xxhash.h"        /* XXH64 */
#include "zstd_internal.h" /* includes zstd.h */
#ifndef ZDICT_STATIC_LINKING_ONLY
#define ZDICT_STATIC_LINKING_ONLY
#endif
#include "zdict.h"

/*-*************************************
 *  Constants
 ***************************************/
#define KB *(1 << 10)
#define MB *(1 << 20)
#define GB *(1U << 30)

#define DICTLISTSIZE_DEFAULT 10000

#define NOISELENGTH 32

static const int g_compressionLevel_default = 3;
static const U32 g_selectivity_default = 9;

/*-*************************************
 *  Console display
 ***************************************/
#define DISPLAY(...)                  \
    {                                 \
        fprintf(stderr, __VA_ARGS__); \
        fflush(stderr);               \
    }
#define DISPLAYLEVEL(l, ...)      \
    if (notificationLevel >= l) { \
        DISPLAY(__VA_ARGS__);     \
    } /* 0 : no display;   1: errors;   2: default;  3: details;  4: debug */

static clock_t ZDICT_clockSpan(clock_t nPrevious) {
    return clock() - nPrevious;
}

static void ZDICT_printHex(const void* ptr, size_t length) {
    const BYTE* const b = (const BYTE*)ptr;
    size_t u;
    for (u = 0; u < length; u++) {
        BYTE c = b[u];
        if (c < 32 || c > 126)
            c = '.'; /* non-printable char */
        DISPLAY("%c", c);
    }
}

/*-********************************************************
 *  Helper functions
 **********************************************************/
unsigned ZDICT_isError(size_t errorCode) {
    return ERR_isError(errorCode);
}

const char* ZDICT_getErrorName(size_t errorCode) {
    return ERR_getErrorName(errorCode);
}

unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize) {
    if (dictSize < 8)
        return 0;
    if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY)
        return 0;
    return MEM_readLE32((const char*)dictBuffer + 4);
}

/*-********************************************************
 *  Dictionary training functions
 **********************************************************/
static unsigned ZDICT_NbCommonBytes(size_t val) {
    if (MEM_isLittleEndian()) {
        if (MEM_64bits()) {
#if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            _BitScanForward64(&r, (U64)val);
            return (unsigned)(r >> 3);
#elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_ctzll((U64)val) >> 3);
#else
            static const int DeBruijnBytePos[64] = {0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
                                                    3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5,
                                                    3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7};
            return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
#endif
        } else { /* 32 bits */
#if defined(_MSC_VER)
            unsigned long r = 0;
            _BitScanForward(&r, (U32)val);
            return (unsigned)(r >> 3);
#elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_ctz((U32)val) >> 3);
#else
            static const int DeBruijnBytePos[32] = {0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1,
                                                    3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1};
            return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
#endif
        }
    } else { /* Big Endian CPU */
        if (MEM_64bits()) {
#if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            _BitScanReverse64(&r, val);
            return (unsigned)(r >> 3);
#elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_clzll(val) >> 3);
#else
            unsigned r;
            const unsigned n32 =
                sizeof(size_t) * 4; /* calculate this way due to compiler complaining in 32-bits mode */
            if (!(val >> n32)) {
                r = 4;
            } else {
                r = 0;
                val >>= n32;
            }
            if (!(val >> 16)) {
                r += 2;
                val >>= 8;
            } else {
                val >>= 24;
            }
            r += (!val);
            return r;
#endif
        } else { /* 32 bits */
#if defined(_MSC_VER)
            unsigned long r = 0;
            _BitScanReverse(&r, (unsigned long)val);
            return (unsigned)(r >> 3);
#elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_clz((U32)val) >> 3);
#else
            unsigned r;
            if (!(val >> 16)) {
                r = 2;
                val >>= 8;
            } else {
                r = 0;
                val >>= 24;
            }
            r += (!val);
            return r;
#endif
        }
    }
}

/*! ZDICT_count() :
    Count the nb of common bytes between 2 pointers.
    Note : this function presumes end of buffer followed by noisy guard band.
*/
static size_t ZDICT_count(const void* pIn, const void* pMatch) {
    const char* const pStart = (const char*)pIn;
    for (;;) {
        size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
        if (!diff) {
            pIn = (const char*)pIn + sizeof(size_t);
            pMatch = (const char*)pMatch + sizeof(size_t);
            continue;
        }
        pIn = (const char*)pIn + ZDICT_NbCommonBytes(diff);
        return (size_t)((const char*)pIn - pStart);
    }
}

typedef struct {
    U32 pos;
    U32 length;
    U32 savings;
} dictItem;

static void ZDICT_initDictItem(dictItem* d) {
    d->pos = 1;
    d->length = 0;
    d->savings = (U32)(-1);
}

#define LLIMIT 64        /* heuristic determined experimentally */
#define MINMATCHLENGTH 7 /* heuristic determined experimentally */
static dictItem ZDICT_analyzePos(BYTE* doneMarks,
                                 const int* suffix,
                                 U32 start,
                                 const void* buffer,
                                 U32 minRatio,
                                 U32 notificationLevel) {
    U32 lengthList[LLIMIT] = {0};
    U32 cumulLength[LLIMIT] = {0};
    U32 savings[LLIMIT] = {0};
    const BYTE* b = (const BYTE*)buffer;
    size_t maxLength = LLIMIT;
    size_t pos = suffix[start];
    U32 end = start;
    dictItem solution;

    /* init */
    memset(&solution, 0, sizeof(solution));
    doneMarks[pos] = 1;

    /* trivial repetition cases */
    if ((MEM_read16(b + pos + 0) == MEM_read16(b + pos + 2)) || (MEM_read16(b + pos + 1) == MEM_read16(b + pos + 3))
        || (MEM_read16(b + pos + 2) == MEM_read16(b + pos + 4))) {
        /* skip and mark segment */
        U16 const pattern16 = MEM_read16(b + pos + 4);
        U32 u, patternEnd = 6;
        while (MEM_read16(b + pos + patternEnd) == pattern16)
            patternEnd += 2;
        if (b[pos + patternEnd] == b[pos + patternEnd - 1])
            patternEnd++;
        for (u = 1; u < patternEnd; u++)
            doneMarks[pos + u] = 1;
        return solution;
    }

    /* look forward */
    {
        size_t length;
        do {
            end++;
            length = ZDICT_count(b + pos, b + suffix[end]);
        } while (length >= MINMATCHLENGTH);
    }

    /* look backward */
    {
        size_t length;
        do {
            length = ZDICT_count(b + pos, b + *(suffix + start - 1));
            if (length >= MINMATCHLENGTH)
                start--;
        } while (length >= MINMATCHLENGTH);
    }

    /* exit if not found a minimum nb of repetitions */
    if (end - start < minRatio) {
        U32 idx;
        for (idx = start; idx < end; idx++)
            doneMarks[suffix[idx]] = 1;
        return solution;
    }

    {
        int i;
        U32 mml;
        U32 refinedStart = start;
        U32 refinedEnd = end;

        DISPLAYLEVEL(4, "\n");
        DISPLAYLEVEL(4,
                     "found %3u matches of length >= %i at pos %7u  ",
                     (unsigned)(end - start),
                     MINMATCHLENGTH,
                     (unsigned)pos);
        DISPLAYLEVEL(4, "\n");

        for (mml = MINMATCHLENGTH;; mml++) {
            BYTE currentChar = 0;
            U32 currentCount = 0;
            U32 currentID = refinedStart;
            U32 id;
            U32 selectedCount = 0;
            U32 selectedID = currentID;
            for (id = refinedStart; id < refinedEnd; id++) {
                if (b[suffix[id] + mml] != currentChar) {
                    if (currentCount > selectedCount) {
                        selectedCount = currentCount;
                        selectedID = currentID;
                    }
                    currentID = id;
                    currentChar = b[suffix[id] + mml];
                    currentCount = 0;
                }
                currentCount++;
            }
            if (currentCount > selectedCount) { /* for last */
                selectedCount = currentCount;
                selectedID = currentID;
            }

            if (selectedCount < minRatio)
                break;
            refinedStart = selectedID;
            refinedEnd = refinedStart + selectedCount;
        }

        /* evaluate gain based on new dict */
        start = refinedStart;
        pos = suffix[refinedStart];
        end = start;
        memset(lengthList, 0, sizeof(lengthList));

        /* look forward */
        {
            size_t length;
            do {
                end++;
                length = ZDICT_count(b + pos, b + suffix[end]);
                if (length >= LLIMIT)
                    length = LLIMIT - 1;
                lengthList[length]++;
            } while (length >= MINMATCHLENGTH);
        }

        /* look backward */
        {
            size_t length = MINMATCHLENGTH;
            while ((length >= MINMATCHLENGTH) & (start > 0)) {
                length = ZDICT_count(b + pos, b + suffix[start - 1]);
                if (length >= LLIMIT)
                    length = LLIMIT - 1;
                lengthList[length]++;
                if (length >= MINMATCHLENGTH)
                    start--;
            }
        }

        /* largest useful length */
        memset(cumulLength, 0, sizeof(cumulLength));
        cumulLength[maxLength - 1] = lengthList[maxLength - 1];
        for (i = (int)(maxLength - 2); i >= 0; i--)
            cumulLength[i] = cumulLength[i + 1] + lengthList[i];

        for (i = LLIMIT - 1; i >= MINMATCHLENGTH; i--)
            if (cumulLength[i] >= minRatio)
                break;
        maxLength = i;

        /* reduce maxLength in case of final into repetitive data */
        {
            U32 l = (U32)maxLength;
            BYTE const c = b[pos + maxLength - 1];
            while (b[pos + l - 2] == c)
                l--;
            maxLength = l;
        }
        if (maxLength < MINMATCHLENGTH)
            return solution; /* skip : no long-enough solution */

        /* calculate savings */
        savings[5] = 0;
        for (i = MINMATCHLENGTH; i <= (int)maxLength; i++)
            savings[i] = savings[i - 1] + (lengthList[i] * (i - 3));

        DISPLAYLEVEL(4,
                     "Selected dict at position %u, of length %u : saves %u (ratio: %.2f)  \n",
                     (unsigned)pos,
                     (unsigned)maxLength,
                     (unsigned)savings[maxLength],
                     (double)savings[maxLength] / maxLength);

        solution.pos = (U32)pos;
        solution.length = (U32)maxLength;
        solution.savings = savings[maxLength];

        /* mark positions done */
        {
            U32 id;
            for (id = start; id < end; id++) {
                U32 p, pEnd, length;
                U32 const testedPos = suffix[id];
                if (testedPos == pos)
                    length = solution.length;
                else {
                    length = (U32)ZDICT_count(b + pos, b + testedPos);
                    if (length > solution.length)
                        length = solution.length;
                }
                pEnd = (U32)(testedPos + length);
                for (p = testedPos; p < pEnd; p++)
                    doneMarks[p] = 1;
            }
        }
    }

    return solution;
}

static int isIncluded(const void* in, const void* container, size_t length) {
    const char* const ip = (const char*)in;
    const char* const into = (const char*)container;
    size_t u;

    for (u = 0; u < length; u++) { /* works because end of buffer is a noisy guard band */
        if (ip[u] != into[u])
            break;
    }

    return u == length;
}

/*! ZDICT_tryMerge() :
    check if dictItem can be merged, do it if possible
    @return : id of destination elt, 0 if not merged
*/
static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer) {
    const U32 tableSize = table->pos;
    const U32 eltEnd = elt.pos + elt.length;
    const char* const buf = (const char*)buffer;

    /* tail overlap */
    U32 u;
    for (u = 1; u < tableSize; u++) {
        if (u == eltNbToSkip)
            continue;
        if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) { /* overlap, existing > new */
            /* append */
            U32 const addedLength = table[u].pos - elt.pos;
            table[u].length += addedLength;
            table[u].pos = elt.pos;
            table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
            table[u].savings += elt.length / 8;                         /* rough approx bonus */
            elt = table[u];
            /* sort : improve rank */
            while ((u > 1) && (table[u - 1].savings < elt.savings))
                table[u] = table[u - 1], u--;
            table[u] = elt;
            return u;
        }
    }

    /* front overlap */
    for (u = 1; u < tableSize; u++) {
        if (u == eltNbToSkip)
            continue;

        if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */
            /* append */
            int const addedLength = (int)eltEnd - (table[u].pos + table[u].length);
            table[u].savings += elt.length / 8; /* rough approx bonus */
            if (addedLength > 0) {              /* otherwise, elt fully included into existing */
                table[u].length += addedLength;
                table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
            }
            /* sort : improve rank */
            elt = table[u];
            while ((u > 1) && (table[u - 1].savings < elt.savings))
                table[u] = table[u - 1], u--;
            table[u] = elt;
            return u;
        }

        if (MEM_read64(buf + table[u].pos) == MEM_read64(buf + elt.pos + 1)) {
            if (isIncluded(buf + table[u].pos, buf + elt.pos + 1, table[u].length)) {
                size_t const addedLength = MAX((int)elt.length - (int)table[u].length, 1);
                table[u].pos = elt.pos;
                table[u].savings += (U32)(elt.savings * addedLength / elt.length);
                table[u].length = MIN(elt.length, table[u].length + 1);
                return u;
            }
        }
    }

    return 0;
}

static void ZDICT_removeDictItem(dictItem* table, U32 id) {
    /* convention : table[0].pos stores nb of elts */
    U32 const max = table[0].pos;
    U32 u;
    if (!id)
        return; /* protection, should never happen */
    for (u = id; u < max - 1; u++)
        table[u] = table[u + 1];
    table->pos--;
}

static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer) {
    /* merge if possible */
    U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
    if (mergeId) {
        U32 newMerge = 1;
        while (newMerge) {
            newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
            if (newMerge)
                ZDICT_removeDictItem(table, mergeId);
            mergeId = newMerge;
        }
        return;
    }

    /* insert */
    {
        U32 current;
        U32 nextElt = table->pos;
        if (nextElt >= maxSize)
            nextElt = maxSize - 1;
        current = nextElt - 1;
        while (table[current].savings < elt.savings) {
            table[current + 1] = table[current];
            current--;
        }
        table[current + 1] = elt;
        table->pos = nextElt + 1;
    }
}

static U32 ZDICT_dictSize(const dictItem* dictList) {
    U32 u, dictSize = 0;
    for (u = 1; u < dictList[0].pos; u++)
        dictSize += dictList[u].length;
    return dictSize;
}

static size_t ZDICT_trainBuffer_legacy(dictItem* dictList,
                                       U32 dictListSize,
                                       const void* const buffer,
                                       size_t bufferSize, /* buffer must end with noisy guard band */
                                       const size_t* fileSizes,
                                       unsigned nbFiles,
                                       unsigned minRatio,
                                       U32 notificationLevel) {
    int* const suffix0 = (int*)malloc((bufferSize + 2) * sizeof(*suffix0));
    int* const suffix = suffix0 + 1;
    U32* reverseSuffix = (U32*)malloc((bufferSize) * sizeof(*reverseSuffix));
    BYTE* doneMarks = (BYTE*)malloc((bufferSize + 16) * sizeof(*doneMarks)); /* +16 for overflow security */
    U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos));
    size_t result = 0;
    clock_t displayClock = 0;
    clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10;

#define DISPLAYUPDATE(l, ...)                              \
    if (notificationLevel >= l) {                          \
        if (ZDICT_clockSpan(displayClock) > refreshRate) { \
            displayClock = clock();                        \
            DISPLAY(__VA_ARGS__);                          \
            if (notificationLevel >= 4)                    \
                fflush(stderr);                            \
        }                                                  \
    }

    /* init */
    DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
    if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
        result = ERROR(memory_allocation);
        goto _cleanup;
    }
    if (minRatio < MINRATIO)
        minRatio = MINRATIO;
    memset(doneMarks, 0, bufferSize + 16);

    /* limit sample set size (divsufsort limitation)*/
    if (bufferSize > ZDICT_MAX_SAMPLES_SIZE)
        DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE >> 20));
    while (bufferSize > ZDICT_MAX_SAMPLES_SIZE)
        bufferSize -= fileSizes[--nbFiles];

    /* sort */
    DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize >> 20));
    {
        int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0);
        if (divSuftSortResult != 0) {
            result = ERROR(GENERIC);
            goto _cleanup;
        }
    }
    suffix[bufferSize] = (int)bufferSize; /* leads into noise */
    suffix0[0] = (int)bufferSize;         /* leads into noise */
    /* build reverse suffix sort */
    {
        size_t pos;
        for (pos = 0; pos < bufferSize; pos++)
            reverseSuffix[suffix[pos]] = (U32)pos;
        /* note filePos tracks borders between samples.
           It's not used at this stage, but planned to become useful in a later update */
        filePos[0] = 0;
        for (pos = 1; pos < nbFiles; pos++)
            filePos[pos] = (U32)(filePos[pos - 1] + fileSizes[pos - 1]);
    }

    DISPLAYLEVEL(2, "finding patterns ... \n");
    DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio);

    {
        U32 cursor;
        for (cursor = 0; cursor < bufferSize;) {
            dictItem solution;
            if (doneMarks[cursor]) {
                cursor++;
                continue;
            }
            solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel);
            if (solution.length == 0) {
                cursor++;
                continue;
            }
            ZDICT_insertDictItem(dictList, dictListSize, solution, buffer);
            cursor += solution.length;
            DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100);
        }
    }

_cleanup:
    free(suffix0);
    free(reverseSuffix);
    free(doneMarks);
    free(filePos);
    return result;
}

static void ZDICT_fillNoise(void* buffer, size_t length) {
    unsigned const prime1 = 2654435761U;
    unsigned const prime2 = 2246822519U;
    unsigned acc = prime1;
    size_t p = 0;
    for (p = 0; p < length; p++) {
        acc *= prime2;
        ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21);
    }
}

typedef struct {
    ZSTD_CDict* dict; /* dictionary */
    ZSTD_CCtx* zc;    /* working context */
    void* workPlace;  /* must be ZSTD_BLOCKSIZE_MAX allocated */
} EStats_ress_t;

#define MAXREPOFFSET 1024

static void ZDICT_countEStats(EStats_ress_t esr,
                              ZSTD_parameters params,
                              unsigned* countLit,
                              unsigned* offsetcodeCount,
                              unsigned* matchlengthCount,
                              unsigned* litlengthCount,
                              U32* repOffsets,
                              const void* src,
                              size_t srcSize,
                              U32 notificationLevel) {
    size_t const blockSizeMax = MIN(ZSTD_BLOCKSIZE_MAX, 1 << params.cParams.windowLog);
    size_t cSize;

    if (srcSize > blockSizeMax)
        srcSize = blockSizeMax; /* protection vs large samples */
    {
        size_t const errorCode = ZSTD_compressBegin_usingCDict(esr.zc, esr.dict);
        if (ZSTD_isError(errorCode)) {
            DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n");
            return;
        }
    }
    cSize = ZSTD_compressBlock(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize);
    if (ZSTD_isError(cSize)) {
        DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize);
        return;
    }

    if (cSize) { /* if == 0; block is not compressible */
        const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc);

        /* literals stats */
        {
            const BYTE* bytePtr;
            for (bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
                countLit[*bytePtr]++;
        }

        /* seqStats */
        {
            U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
            ZSTD_seqToCodes(seqStorePtr);

            {
                const BYTE* codePtr = seqStorePtr->ofCode;
                U32 u;
                for (u = 0; u < nbSeq; u++)
                    offsetcodeCount[codePtr[u]]++;
            }

            {
                const BYTE* codePtr = seqStorePtr->mlCode;
                U32 u;
                for (u = 0; u < nbSeq; u++)
                    matchlengthCount[codePtr[u]]++;
            }

            {
                const BYTE* codePtr = seqStorePtr->llCode;
                U32 u;
                for (u = 0; u < nbSeq; u++)
                    litlengthCount[codePtr[u]]++;
            }

            if (nbSeq >= 2) { /* rep offsets */
                const seqDef* const seq = seqStorePtr->sequencesStart;
                U32 offset1 = seq[0].offset - 3;
                U32 offset2 = seq[1].offset - 3;
                if (offset1 >= MAXREPOFFSET)
                    offset1 = 0;
                if (offset2 >= MAXREPOFFSET)
                    offset2 = 0;
                repOffsets[offset1] += 3;
                repOffsets[offset2] += 1;
            }
        }
    }
}

static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles) {
    size_t total = 0;
    unsigned u;
    for (u = 0; u < nbFiles; u++)
        total += fileSizes[u];
    return total;
}

typedef struct {
    U32 offset;
    U32 count;
} offsetCount_t;

static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM + 1], U32 val, U32 count) {
    U32 u;
    table[ZSTD_REP_NUM].offset = val;
    table[ZSTD_REP_NUM].count = count;
    for (u = ZSTD_REP_NUM; u > 0; u--) {
        offsetCount_t tmp;
        if (table[u - 1].count >= table[u].count)
            break;
        tmp = table[u - 1];
        table[u - 1] = table[u];
        table[u] = tmp;
    }
}

/* ZDICT_flatLit() :
 * rewrite `countLit` to contain a mostly flat but still compressible distribution of literals.
 * necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode.
 */
static void ZDICT_flatLit(unsigned* countLit) {
    int u;
    for (u = 1; u < 256; u++)
        countLit[u] = 2;
    countLit[0] = 4;
    countLit[253] = 1;
    countLit[254] = 1;
}

#define OFFCODE_MAX 30 /* only applicable to first block */
static size_t ZDICT_analyzeEntropy(void* dstBuffer,
                                   size_t maxDstSize,
                                   unsigned compressionLevel,
                                   const void* srcBuffer,
                                   const size_t* fileSizes,
                                   unsigned nbFiles,
                                   const void* dictBuffer,
                                   size_t dictBufferSize,
                                   unsigned notificationLevel) {
    unsigned countLit[256];
    HUF_CREATE_STATIC_CTABLE(hufTable, 255);
    unsigned offcodeCount[OFFCODE_MAX + 1];
    short offcodeNCount[OFFCODE_MAX + 1];
    U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
    unsigned matchLengthCount[MaxML + 1];
    short matchLengthNCount[MaxML + 1];
    unsigned litLengthCount[MaxLL + 1];
    short litLengthNCount[MaxLL + 1];
    U32 repOffset[MAXREPOFFSET];
    offsetCount_t bestRepOffset[ZSTD_REP_NUM + 1];
    EStats_ress_t esr = {NULL, NULL, NULL};
    ZSTD_parameters params;
    U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
    size_t pos = 0, errorCode;
    size_t eSize = 0;
    size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
    size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
    BYTE* dstPtr = (BYTE*)dstBuffer;

    /* init */
    DEBUGLOG(4, "ZDICT_analyzeEntropy");
    if (offcodeMax > OFFCODE_MAX) {
        eSize = ERROR(dictionaryCreation_failed);
        goto _cleanup;
    } /* too large dictionary */
    for (u = 0; u < 256; u++)
        countLit[u] = 1; /* any character must be described */
    for (u = 0; u <= offcodeMax; u++)
        offcodeCount[u] = 1;
    for (u = 0; u <= MaxML; u++)
        matchLengthCount[u] = 1;
    for (u = 0; u <= MaxLL; u++)
        litLengthCount[u] = 1;
    memset(repOffset, 0, sizeof(repOffset));
    repOffset[1] = repOffset[4] = repOffset[8] = 1;
    memset(bestRepOffset, 0, sizeof(bestRepOffset));
    if (compressionLevel == 0)
        compressionLevel = g_compressionLevel_default;
    params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);

    esr.dict = ZSTD_createCDict_advanced(dictBuffer,
                                         dictBufferSize,
                                         ZSTD_dlm_byRef,
                                         ZSTD_dct_rawContent,
                                         params.cParams,
                                         ZSTD_defaultCMem);
    esr.zc = ZSTD_createCCtx();
    esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
    if (!esr.dict || !esr.zc || !esr.workPlace) {
        eSize = ERROR(memory_allocation);
        DISPLAYLEVEL(1, "Not enough memory \n");
        goto _cleanup;
    }

    /* collect stats on all samples */
    for (u = 0; u < nbFiles; u++) {
        ZDICT_countEStats(esr,
                          params,
                          countLit,
                          offcodeCount,
                          matchLengthCount,
                          litLengthCount,
                          repOffset,
                          (const char*)srcBuffer + pos,
                          fileSizes[u],
                          notificationLevel);
        pos += fileSizes[u];
    }

    /* analyze, build stats, starting with literals */
    {
        size_t maxNbBits = HUF_buildCTable(hufTable, countLit, 255, huffLog);
        if (HUF_isError(maxNbBits)) {
            eSize = maxNbBits;
            DISPLAYLEVEL(1, " HUF_buildCTable error \n");
            goto _cleanup;
        }
        if (maxNbBits == 8) { /* not compressible : will fail on HUF_writeCTable() */
            DISPLAYLEVEL(
                2,
                "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n");
            ZDICT_flatLit(countLit); /* replace distribution by a fake "mostly flat but still compressible"
                                        distribution, that HUF_writeCTable() can encode */
            maxNbBits = HUF_buildCTable(hufTable, countLit, 255, huffLog);
            assert(maxNbBits == 9);
        }
        huffLog = (U32)maxNbBits;
    }

    /* looking for most common first offsets */
    {
        U32 offset;
        for (offset = 1; offset < MAXREPOFFSET; offset++)
            ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
    }
    /* note : the result of this phase should be used to better appreciate the impact on statistics */

    total = 0;
    for (u = 0; u <= offcodeMax; u++)
        total += offcodeCount[u];
    errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n");
        goto _cleanup;
    }
    Offlog = (U32)errorCode;

    total = 0;
    for (u = 0; u <= MaxML; u++)
        total += matchLengthCount[u];
    errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n");
        goto _cleanup;
    }
    mlLog = (U32)errorCode;

    total = 0;
    for (u = 0; u <= MaxLL; u++)
        total += litLengthCount[u];
    errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n");
        goto _cleanup;
    }
    llLog = (U32)errorCode;

    /* write result to buffer */
    {
        size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog);
        if (HUF_isError(hhSize)) {
            eSize = hhSize;
            DISPLAYLEVEL(1, "HUF_writeCTable error \n");
            goto _cleanup;
        }
        dstPtr += hhSize;
        maxDstSize -= hhSize;
        eSize += hhSize;
    }

    {
        size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
        if (FSE_isError(ohSize)) {
            eSize = ohSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n");
            goto _cleanup;
        }
        dstPtr += ohSize;
        maxDstSize -= ohSize;
        eSize += ohSize;
    }

    {
        size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
        if (FSE_isError(mhSize)) {
            eSize = mhSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n");
            goto _cleanup;
        }
        dstPtr += mhSize;
        maxDstSize -= mhSize;
        eSize += mhSize;
    }

    {
        size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
        if (FSE_isError(lhSize)) {
            eSize = lhSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n");
            goto _cleanup;
        }
        dstPtr += lhSize;
        maxDstSize -= lhSize;
        eSize += lhSize;
    }

    if (maxDstSize < 12) {
        eSize = ERROR(dstSize_tooSmall);
        DISPLAYLEVEL(1, "not enough space to write RepOffsets \n");
        goto _cleanup;
    }
#if 0
    MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
    MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
    MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
#else
    /* at this stage, we don't use the result of "most common first offset",
       as the impact of statistics is not properly evaluated */
    MEM_writeLE32(dstPtr + 0, repStartValue[0]);
    MEM_writeLE32(dstPtr + 4, repStartValue[1]);
    MEM_writeLE32(dstPtr + 8, repStartValue[2]);
#endif
    eSize += 12;

_cleanup:
    ZSTD_freeCDict(esr.dict);
    ZSTD_freeCCtx(esr.zc);
    free(esr.workPlace);

    return eSize;
}

size_t ZDICT_finalizeDictionary(void* dictBuffer,
                                size_t dictBufferCapacity,
                                const void* customDictContent,
                                size_t dictContentSize,
                                const void* samplesBuffer,
                                const size_t* samplesSizes,
                                unsigned nbSamples,
                                ZDICT_params_t params) {
    size_t hSize;
#define HBUFFSIZE 256 /* should prove large enough for all entropy headers */
    BYTE header[HBUFFSIZE];
    int const compressionLevel = (params.compressionLevel == 0) ? g_compressionLevel_default : params.compressionLevel;
    U32 const notificationLevel = params.notificationLevel;

    /* check conditions */
    DEBUGLOG(4, "ZDICT_finalizeDictionary");
    if (dictBufferCapacity < dictContentSize)
        return ERROR(dstSize_tooSmall);
    if (dictContentSize < ZDICT_CONTENTSIZE_MIN)
        return ERROR(srcSize_wrong);
    if (dictBufferCapacity < ZDICT_DICTSIZE_MIN)
        return ERROR(dstSize_tooSmall);

    /* dictionary header */
    MEM_writeLE32(header, ZSTD_MAGIC_DICTIONARY);
    {
        U64 const randomID = XXH64(customDictContent, dictContentSize, 0);
        U32 const compliantID = (randomID % ((1U << 31) - 32768)) + 32768;
        U32 const dictID = params.dictID ? params.dictID : compliantID;
        MEM_writeLE32(header + 4, dictID);
    }
    hSize = 8;

    /* entropy tables */
    DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
    DISPLAYLEVEL(2, "statistics ... \n");
    {
        size_t const eSize = ZDICT_analyzeEntropy(header + hSize,
                                                  HBUFFSIZE - hSize,
                                                  compressionLevel,
                                                  samplesBuffer,
                                                  samplesSizes,
                                                  nbSamples,
                                                  customDictContent,
                                                  dictContentSize,
                                                  notificationLevel);
        if (ZDICT_isError(eSize))
            return eSize;
        hSize += eSize;
    }

    /* copy elements in final buffer ; note : src and dst buffer can overlap */
    if (hSize + dictContentSize > dictBufferCapacity)
        dictContentSize = dictBufferCapacity - hSize;
    {
        size_t const dictSize = hSize + dictContentSize;
        char* dictEnd = (char*)dictBuffer + dictSize;
        memmove(dictEnd - dictContentSize, customDictContent, dictContentSize);
        memcpy(dictBuffer, header, hSize);
        return dictSize;
    }
}

static size_t ZDICT_addEntropyTablesFromBuffer_advanced(void* dictBuffer,
                                                        size_t dictContentSize,
                                                        size_t dictBufferCapacity,
                                                        const void* samplesBuffer,
                                                        const size_t* samplesSizes,
                                                        unsigned nbSamples,
                                                        ZDICT_params_t params) {
    int const compressionLevel = (params.compressionLevel == 0) ? g_compressionLevel_default : params.compressionLevel;
    U32 const notificationLevel = params.notificationLevel;
    size_t hSize = 8;

    /* calculate entropy tables */
    DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
    DISPLAYLEVEL(2, "statistics ... \n");
    {
        size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer + hSize,
                                                  dictBufferCapacity - hSize,
                                                  compressionLevel,
                                                  samplesBuffer,
                                                  samplesSizes,
                                                  nbSamples,
                                                  (char*)dictBuffer + dictBufferCapacity - dictContentSize,
                                                  dictContentSize,
                                                  notificationLevel);
        if (ZDICT_isError(eSize))
            return eSize;
        hSize += eSize;
    }

    /* add dictionary header (after entropy tables) */
    MEM_writeLE32(dictBuffer, ZSTD_MAGIC_DICTIONARY);
    {
        U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0);
        U32 const compliantID = (randomID % ((1U << 31) - 32768)) + 32768;
        U32 const dictID = params.dictID ? params.dictID : compliantID;
        MEM_writeLE32((char*)dictBuffer + 4, dictID);
    }

    if (hSize + dictContentSize < dictBufferCapacity)
        memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
    return MIN(dictBufferCapacity, hSize + dictContentSize);
}

/* Hidden declaration for dbio.c */
size_t ZDICT_trainFromBuffer_unsafe_legacy(void* dictBuffer,
                                           size_t maxDictSize,
                                           const void* samplesBuffer,
                                           const size_t* samplesSizes,
                                           unsigned nbSamples,
                                           ZDICT_legacy_params_t params);
/*! ZDICT_trainFromBuffer_unsafe_legacy() :
 *   Warning : `samplesBuffer` must be followed by noisy guard band.
 *   @return : size of dictionary, or an error code which can be tested with ZDICT_isError()
 */
size_t ZDICT_trainFromBuffer_unsafe_legacy(void* dictBuffer,
                                           size_t maxDictSize,
                                           const void* samplesBuffer,
                                           const size_t* samplesSizes,
                                           unsigned nbSamples,
                                           ZDICT_legacy_params_t params) {
    U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize / 16));
    dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList));
    unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel;
    unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity;
    size_t const targetDictSize = maxDictSize;
    size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
    size_t dictSize = 0;
    U32 const notificationLevel = params.zParams.notificationLevel;

    /* checks */
    if (!dictList)
        return ERROR(memory_allocation);
    if (maxDictSize < ZDICT_DICTSIZE_MIN) {
        free(dictList);
        return ERROR(dstSize_tooSmall);
    } /* requested dictionary size is too small */
    if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) {
        free(dictList);
        return ERROR(dictionaryCreation_failed);
    } /* not enough source to create dictionary */

    /* init */
    ZDICT_initDictItem(dictList);

    /* build dictionary */
    ZDICT_trainBuffer_legacy(dictList,
                             dictListSize,
                             samplesBuffer,
                             samplesBuffSize,
                             samplesSizes,
                             nbSamples,
                             minRep,
                             notificationLevel);

    /* display best matches */
    if (params.zParams.notificationLevel >= 3) {
        unsigned const nb = MIN(25, dictList[0].pos);
        unsigned const dictContentSize = ZDICT_dictSize(dictList);
        unsigned u;
        DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", (unsigned)dictList[0].pos - 1, dictContentSize);
        DISPLAYLEVEL(3, "list %u best segments \n", nb - 1);
        for (u = 1; u < nb; u++) {
            unsigned const pos = dictList[u].pos;
            unsigned const length = dictList[u].length;
            U32 const printedLength = MIN(40, length);
            if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) {
                free(dictList);
                return ERROR(GENERIC); /* should never happen */
            }
            DISPLAYLEVEL(3,
                         "%3u:%3u bytes at pos %8u, savings %7u bytes |",
                         u,
                         length,
                         pos,
                         (unsigned)dictList[u].savings);
            ZDICT_printHex((const char*)samplesBuffer + pos, printedLength);
            DISPLAYLEVEL(3, "| \n");
        }
    }

    /* create dictionary */
    {
        unsigned dictContentSize = ZDICT_dictSize(dictList);
        if (dictContentSize < ZDICT_CONTENTSIZE_MIN) {
            free(dictList);
            return ERROR(dictionaryCreation_failed);
        } /* dictionary content too small */
        if (dictContentSize < targetDictSize / 4) {
            DISPLAYLEVEL(2,
                         "!  warning : selected content significantly smaller than requested (%u < %u) \n",
                         dictContentSize,
                         (unsigned)maxDictSize);
            if (samplesBuffSize < 10 * targetDictSize)
                DISPLAYLEVEL(2,
                             "!  consider increasing the number of samples (total size : %u MB)\n",
                             (unsigned)(samplesBuffSize >> 20));
            if (minRep > MINRATIO) {
                DISPLAYLEVEL(2,
                             "!  consider increasing selectivity to produce larger dictionary (-s%u) \n",
                             selectivity + 1);
                DISPLAYLEVEL(
                    2,
                    "!  note : larger dictionaries are not necessarily better, test its efficiency on samples \n");
            }
        }

        if ((dictContentSize > targetDictSize * 3) && (nbSamples > 2 * MINRATIO) && (selectivity > 1)) {
            unsigned proposedSelectivity = selectivity - 1;
            while ((nbSamples >> proposedSelectivity) <= MINRATIO) {
                proposedSelectivity--;
            }
            DISPLAYLEVEL(2,
                         "!  note : calculated dictionary significantly larger than requested (%u > %u) \n",
                         dictContentSize,
                         (unsigned)maxDictSize);
            DISPLAYLEVEL(2,
                         "!  consider increasing dictionary size, or produce denser dictionary (-s%u) \n",
                         proposedSelectivity);
            DISPLAYLEVEL(2, "!  always test dictionary efficiency on real samples \n");
        }

        /* limit dictionary size */
        {
            U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */
            U32 currentSize = 0;
            U32 n;
            for (n = 1; n < max; n++) {
                currentSize += dictList[n].length;
                if (currentSize > targetDictSize) {
                    currentSize -= dictList[n].length;
                    break;
                }
            }
            dictList->pos = n;
            dictContentSize = currentSize;
        }

        /* build dict content */
        {
            U32 u;
            BYTE* ptr = (BYTE*)dictBuffer + maxDictSize;
            for (u = 1; u < dictList->pos; u++) {
                U32 l = dictList[u].length;
                ptr -= l;
                if (ptr < (BYTE*)dictBuffer) {
                    free(dictList);
                    return ERROR(GENERIC);
                } /* should not happen */
                memcpy(ptr, (const char*)samplesBuffer + dictList[u].pos, l);
            }
        }

        dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer,
                                                             dictContentSize,
                                                             maxDictSize,
                                                             samplesBuffer,
                                                             samplesSizes,
                                                             nbSamples,
                                                             params.zParams);
    }

    /* clean up */
    free(dictList);
    return dictSize;
}

/* ZDICT_trainFromBuffer_legacy() :
 * issue : samplesBuffer need to be followed by a noisy guard band.
 * work around : duplicate the buffer, and add the noise */
size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer,
                                    size_t dictBufferCapacity,
                                    const void* samplesBuffer,
                                    const size_t* samplesSizes,
                                    unsigned nbSamples,
                                    ZDICT_legacy_params_t params) {
    size_t result;
    void* newBuff;
    size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
    if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE)
        return 0; /* not enough content => no dictionary */

    newBuff = malloc(sBuffSize + NOISELENGTH);
    if (!newBuff)
        return ERROR(memory_allocation);

    memcpy(newBuff, samplesBuffer, sBuffSize);
    ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */

    result =
        ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff, samplesSizes, nbSamples, params);
    free(newBuff);
    return result;
}

size_t ZDICT_trainFromBuffer(void* dictBuffer,
                             size_t dictBufferCapacity,
                             const void* samplesBuffer,
                             const size_t* samplesSizes,
                             unsigned nbSamples) {
    ZDICT_fastCover_params_t params;
    DEBUGLOG(3, "ZDICT_trainFromBuffer");
    memset(&params, 0, sizeof(params));
    params.d = 8;
    params.steps = 4;
    /* Default to level 6 since no compression level information is available */
    params.zParams.compressionLevel = 3;
#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 1)
    params.zParams.notificationLevel = DEBUGLEVEL;
#endif
    return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer,
                                                   dictBufferCapacity,
                                                   samplesBuffer,
                                                   samplesSizes,
                                                   nbSamples,
                                                   &params);
}

size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer,
                                        size_t dictContentSize,
                                        size_t dictBufferCapacity,
                                        const void* samplesBuffer,
                                        const size_t* samplesSizes,
                                        unsigned nbSamples) {
    ZDICT_params_t params;
    memset(&params, 0, sizeof(params));
    return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer,
                                                     dictContentSize,
                                                     dictBufferCapacity,
                                                     samplesBuffer,
                                                     samplesSizes,
                                                     nbSamples,
                                                     params);
}
